Recent years have seen the rapid advancement and proliferation of electronic devices, which devices often require the updating of the resident firmware, operating code, applications or other software loaded thereon, collectively, “binary images”, or simply “images”. Moreover, installing and updating of such binary images is becoming more routine as advancements applicable to a particular device far outpace the rate at which it is desirable to retire the unit and replace it with an entirely new unit. Instead, the operating software and other applications are updated on the device to create a new binary image needing updating or installation on such device.
Moreover, for many devices for which updating the binary image is desirable, these same devices may be remotely located and it is not practical for many reasons to return or collect the device in order that it can be directly connected to a host updating machine or system.
Additionally, with limited memory on the device itself, whether it is a mobile phone, PDA, pager or any other variety of small form factor portable device, delivery of an entire new image is often infeasible due to the capacity limitations of the device.
Manufactures are now deploying portable communication devices employing flash memory. Additionally, manufactures are using compression techniques, such as Lempel-Ziv-Welch (LZW) and similar techniques, to store programs and data within the device. Compression is used in order to reduce the size and therefore cost of the storage media.
In principle data compression applies a reversible transformation to a particular revision of the data. However, today's compression techniques are problematic because when the new image is only slightly different from original image the compression algorithm will often result in the compressed new image being very substantially different from the original image, and in the degenerate case, every byte changes. This is particularly the case with compression based on LZW or similar techniques, and arises because a change in the symbol table generated during the encoding causes cascading further changes to the symbol table, and within a short distance of a changed byte in the new image relative to original image, the encoded symbol stream in compressed new image will be completely unrelated to the corresponding position in the compressed original image.
Accordingly there is a need for an efficient, effective and reliable system and method for data compression of binary data, which preserves similarity in the compressed forms of the compressed original image and the compressed new image when the new image and the original image are similar. For example, applying a small software bug fix or patch is one case where the original image and the new image differ only slightly. Thus, when the compressed image forms are processed by a binary differencing method the resultant delta or update package will be small.
A known manner in reducing the size of a new image update is to use a differencing algorithm or binary differencing engine (BDE) to compare the current or existing binary image with the new binary image to produce a list of differences. Such differences, in a general sense, are typically output or expressed as sequences or sets of ADD and COPY operations such that the new image can be created by re-combining binary strings copied from image sequences resident on the device in the original image and interspersing them with binary sequences from the new image for which a suitable copy string was not available in the old image. Additionally, and Update Encoder communicating with the BDE combines additional encoding information to the select instructions from the BDE and incorporates other operations derived from additional information to ultimately create the update package. One efficient approach to generating update packages is described in U.S. patent application Ser. No. 10/676,483 entitled “Efficient System and Method for Updating a Memory Device”, filed Sep. 30, 2003, the disclosure of which is incorporated herein by reference.
The need therefore is for a system that reduces the size impact of systematic changes on the final update package, and optimizes the size and number of operations to find the most effective and minimized update package size for any given compressed original image and compressed new image; resulting in update package sizes which reflect the size of the change made to the compressed image at the raw binary level.